package Heap;

import java.util.Arrays;

public class TestHeap {
    public int[]elem;
    public int useSize;
    public TestHeap(){
        this.elem= new int[10];
    }
    //创建大根堆
    public void createHeap(int[] array){
        for (int i = 0; i <array.length ; i++) {
            elem[i]=array[i];
            useSize++;
        }
        for (int parent=(array.length-1-1)/2;parent>=0;parent--){
            adjustDown(parent,this.useSize);
        }
    }
    //向下调整
    private void adjustDown(int root,int len){
        int parent=root;
        int child=2*root+1;
        while (child<len){
            if(child+1<len&&this.elem[child]<this.elem[child+1]){
                child++;
            }
            if(this.elem[parent]<this.elem[child]){
                int tmp=this.elem[parent];
                this.elem[parent]=this.elem[child];
                this.elem[child]=tmp;
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

    //向上调整
    void adjustUp(int child){
        int parent=(child-1)/2;
        while (parent>=0){
            if(this.elem[child]>this.elem[parent]){
                int tmp=this.elem[child];
                this.elem[child]=this.elem[parent];
                this.elem[parent]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }
    public void push(int val){
        if(isFull()){
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
        }

        this.elem[this.useSize]=val;
        useSize++;
        adjustUp(this.useSize-1);
    }
    public boolean isFull(){
        if(useSize==this.elem.length){
            return true;
        }
        return false;
    }
    //出队
    public void pop(){
        if(isEmpty()) return;
        int tmp=this.elem[0];
        this.elem[0]=this.elem[this.useSize-1];
        this.elem[this.useSize-1]=tmp;
        this.useSize--;//删除了
        adjustDown(0,this.useSize);//此次传的是长度
    }
    public boolean isEmpty(){
        return this.useSize==0;
    }
    public int peek(){
        if(isEmpty()) return -1;
        return this.elem[0];
      }
      //堆排序
    //一定先建大堆
    //0和最后交换
    //再次整理成大堆
      public void heapSort(){

        int end=this.useSize-1;
        while (end>0) {//换到0就不换了
            int tmp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = tmp;
            adjustDown(0, end);
            end--;
        }
      }
}
